.

iT邦幫忙

2022 iThome 鐵人賽

DAY 5
2
自我挑戰組

挑戰 blind 75: 以圖解方式練習解題系列 第 16

圖解 blind 75: Sliding-Window - Best Time to Buy and Sell Stock(1/2)

  • 分享至 

  • xImage
  •  

Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Examples

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

  • 1 <= prices.length <= 10^5
  • 0 <= prices[i] <= 10^4

解析

給定一個正整數陣列 prices

每個 prices[i] 代表第 i 日股票的價錢

假設必須要選某一天 假設是 j 買入 還有另一天 k 賣出 且 j < k

則獲利 = height[k] - height[j]

要求寫出一個演算法算出最大的獲利

已知如果要找出最大獲利

就必須在每個 i 找到一個 k 使得 k > i 且 height[k] > height[i] 讓 height[k] 最大化

這時可以透過 slide window 的技巧計算每個 slide window 內的最大值

逐步比較出整體的最大值

因為知道 買入日比需要在賣出日之前

所以初始化 buy_min = 0, sell_max = 1, max_profit = 0

sell_max 從 1.. len(prices) - 1 做以下運算

如果 prices[sell_max] > prices[buy_min] 則更新 max_profit = max(max_profit, prices[sell_max] - prices[buy_min])

如果 prices[sell_max] ≤ prices[buy_min] 代表 當下 sell_max 可能成為下個最小 buy_min 所以更新 buy_min = sell_max

當所有值比完 回傳 max_profit

透過 Sliding Window 演算法 每次可以找到在某個大的賣出值最大獲利

透過這個方式可以只走訪過 prices 陣列一次就找到最大獲利

時間複雜度是 O(n)

比窮舉法針對每個買入價去找尋之後的最大賣出價需要 O(n^2) 還要有效率

空間複雜度是 O(1), 因為只需要紀錄最小買入價 還有最大賣出的價錢

程式碼

package sol

func maxProfit(prices []int) int {
	buy, max_profit := 0, 0
	n := len(prices)
	var max = func(a, b int) int {
		if a < b {
			return b
		}
		return a
	}
	for sell := 1; sell < n; sell++ {
		if prices[sell] > prices[buy] {
			max_profit = max(max_profit, prices[sell]-prices[buy])
		} else { // prices[sell] is current smallest
			buy = sell
		}
	}
	return max_profit
}

困難點

  1. 要看出 profit 的buy 與 sell 的關係
  2. 要看出 max profit 的形成條件

Solve Point

  • [x] 初始化 buy =0, sell = 1, maxProfit = 0
  • [x] 從 sell = 1..len(prices) 做以下運算
  • [x] 當 prices[sell] > prices[buy] 時,更新 maxProfit = max(maxProfit, prices[sell] - prices[buy])
  • [x] 當 prices[sell] ≤ prices[buy] 時, 當下 prices[sell] 是最小值 。所以更新 buy = sell
  • [x] 當比完所有 sell 時,回傳 maxProfit

感想

寫到這題最大獲利

我想到一個句經典名句

https://memeprod.sgp1.digitaloceanspaces.com/user-wtf/1619756847315.jpg


上一篇
圖解 blind 75: Sliding-Window 策略講解
下一篇
圖解 blind 75: Sliding-Window - Longest Substring Without Repeating Characters(2/2)
系列文
挑戰 blind 75: 以圖解方式練習解題93
.
圖片
  直播研討會

尚未有邦友留言

立即登入留言